package apii.algorithm.colmo;

import java.sql.Connection;
import java.sql.SQLException;
import java.util.Iterator;
import java.util.LinkedList;

import apii.algorithm.Algorithm;
import apii.algorithm.ProgressMonitor;

/**
 * 
 * @author evgeniy
 * 
 */
public class ColmogorovDiffAlgo implements Algorithm {

	private static final int EXPECTED_ALPHABETH_SIZE = 400;
	private static final int INITIAL_BUFFER_SIZE = 1000;

	private static Dictionary d = new Dictionary();

	@Override
	public void inspect(Connection c, int codeId, Iterator<Integer> codeIds,
			ProgressMonitor pm) throws SQLException {
		// TODO Auto-generated method stub
		
	}

	public static int getDifficulty(int[] x, BufferProvider bp) {
		return getDifficulty(d, x, bp);
	}
	
	public static double getJointDifficulty(int[] x, int []y, BufferProvider bp) {
		
		// просто закодить x и y подряд
		Dictionary d = new Dictionary();
		double xDiff = getDifficulty(d, x, bp);
		return 0;
	}

	public static double getConditionalDifficulty(int[] x, int[] y, int[] buffer) {
		BufferProvider bp = new BufferProvider();
		bp.buffer = buffer;

		// create the dictionary with subwords of y
		Dictionary yD = new Dictionary();

		for (double i = 2; i < y.length; i *= 2) {
			for (int j = 0; j + i - 1 < y.length; j++) {
				yD.putWord(y, j, j + (int) i - 1);
			}
		}

		return getDifficulty(yD, x, bp);
	}

	public static double getConditionalDifficulty(int[] x, int[] y,
			BufferProvider bp) {
		

		// create the dictionary with subwords of y
		Dictionary yD = new Dictionary();

		for (double i = 2; i < y.length; i *= 2) {
			for (int j = 0; j + i - 1 < y.length; j++) {
				yD.putWord(y, j, j + (int) i - 1);
			}
		}

		return getDifficulty(yD, x, bp);
	}

	public static int getDifficulty(Dictionary d, int[] x, BufferProvider bp) {
		final int KEEP_SEEKING = 1;
		final int NOT_FOUND = 2;
		final int WORD_END = 3;
		int state = KEEP_SEEKING;

		double resultSize = 0;

		// need to compress x
		int nextXIndex = 0;

		// go over the word
		while (nextXIndex < x.length) {

			// check find max string from dictionary in x
			int bufferTop = -1;
			DictionaryLvl currentLvl = null;
			DictionaryLvl parentLvl = null;
			state = KEEP_SEEKING;
			while (state == KEEP_SEEKING) {
				// get the current level of dictionary
				//
				// if there is only a start: empty buffer
				if (bufferTop == -1) {
					currentLvl = d.getFirstLvl(x[nextXIndex]);
				} else { // non-empty buffer
					parentLvl = currentLvl;
					currentLvl = currentLvl.getChild(x[nextXIndex]);
				}

				// parse the gotten dictionary level
				if (currentLvl == null) {
					// the dictionary does not contain next symbol
					state = NOT_FOUND;
				} else { // the dictionary contains next symbol. keep seeking
					// add current symbol to buffer
					//
					// handle the buffer size
					if (bufferTop + 1 >= bp.buffer.length) {
						int newBuffer[] = new int[2 * bp.buffer.length];
						copy(newBuffer, bp.buffer, 0, 0, bufferTop + 1);
						bp.buffer = newBuffer;
					}
					bufferTop++;
					bp.buffer[bufferTop] = x[nextXIndex];
					nextXIndex++;
				}
				if (nextXIndex >= x.length) {
					state = WORD_END;
				}
			}

			if (state == WORD_END) {
				// encode current buffer
				// resultSize += Math.log((double) currentLvl.ccn);
				resultSize++;
			} else if (state == NOT_FOUND) {
				// encode current buffer
				// resultSize += Math.log((double) parentLvl.ccn);
				resultSize++;
				// enlarge the dictionary;
				DictionaryLvl newLvl = parentLvl.putChild(x[nextXIndex]);
				newLvl.ccn = d.getCCN();
			} else {
				throw new Error();
			}
		}

		return (int) resultSize;
	}
	
	/**
	 * 
	 * @param code1
	 * @param code2
	 */
	private void compareCodes(int[] x, int[] y, BufferProvider bp) {
		double xDiff = getDifficulty(x, bp);
		double xCondYDiff = getConditionalDifficulty(x, y, bp);
		double xyJointDiff = getJointDifficulty(x, y, bp);
	}

	// private static void outputBuffer(int[] buffer, int bufferTop) {
	// for (int i = 0; i <= bufferTop; i++) {
	// System.out.print(buffer[i] + ", ");
	// }
	// System.out.println(";");
	// }

	private static void copy(int[] a1, int[] a2, int start1, int start2,
			int size) {
		for (int i = 0; i < size; i++) {
			a1[start1 + i] = a2[start2 + i];
		}
	}

	/**
	 * 
	 * @author evgeniy
	 * 
	 */
	private static class Dictionary {

		public DictionaryLvl firstLvls[];
		public int ccn = 0;

		public Dictionary() {
			createVirginDictionary();
		}

		public DictionaryLvl getFirstLvl(int symbol) {
			for (DictionaryLvl lvl : firstLvls) {
				if (lvl.symbol == symbol) {
					return lvl;
				}
			}
			return null;
		}

		public int getCCN() {
			ccn++;
			return ccn;
		}

		// ///////////////////////////////////////////////////////////

		/**
		 * 
		 * @param word
		 * @param lastIndex
		 *            - the index of the last symbol
		 * @return false if the word[0..lastIndex] is in the dictionary
		 * @return true if the word[0..lastIndex] is not in the dictionary +
		 *         adds it into the dictionary
		 * @throws IllegalArgumentException
		 *             if the word[0..lastIndex-1] is not in the dictionary
		 */
		public boolean putWord(int word[], int firstIndex, int lastIndex)
				throws IllegalArgumentException {

			if (firstIndex < 0) {
				throw new IllegalArgumentException();
			}
			if (lastIndex >= word.length) {
				throw new IllegalArgumentException();
			}

			// get the first level
			DictionaryLvl currentLvl = null;
			for (int i = 0; i < firstLvls.length; i++) {
				if (firstLvls[i].symbol == word[0]) {
					currentLvl = firstLvls[i];
					break;
				}
			}
			if (currentLvl == null) {// which means it is not found
				throw new IllegalArgumentException();
			}

			// now we have the first (lvlIndex=0) level for our word; go ahead
			// for next levelz
			int lvlIndex = 1;
			DictionaryLvl prevLvl = null;
			while (lvlIndex < lastIndex) {
				prevLvl = currentLvl;
				currentLvl = currentLvl.getChild(word[lvlIndex]);
				if (currentLvl == null) {
					currentLvl = prevLvl.putChild(word[lvlIndex]);
					currentLvl.ccn = getCCN();
				}
				lvlIndex++;
			}

			return true;
		}

		public void createVirginDictionary() {
			firstLvls = new DictionaryLvl[EXPECTED_ALPHABETH_SIZE];
			for (int i = 0; i < firstLvls.length; i++) {
				firstLvls[i] = new DictionaryLvl(i);
				firstLvls[i].ccn = getCCN();
			}
		}

	}

	/**
	 * 
	 * @author evgeniy
	 * 
	 */
	private static class DictionaryLvl {

		// symbol of this level
		public int symbol;
		// list of children levels
		public LinkedList<DictionaryLvl> lvls = new LinkedList<DictionaryLvl>();
		public int ccn = 0;

		public DictionaryLvl(int symbol) {
			this.symbol = symbol;
		}

		public DictionaryLvl putChild(int symbol) {
			DictionaryLvl result;
			DictionaryLvl ifExistsChild;
			ifExistsChild = getChild(symbol);
			if (ifExistsChild == null) {
				result = new DictionaryLvl(symbol);
				lvls.add(result);
				return result;
			} else {
				return ifExistsChild;
			}
		}

		public DictionaryLvl getChild(int symbol) {
			for (DictionaryLvl currentChildLvl : lvls) {
				if (currentChildLvl.symbol == symbol) {
					return currentChildLvl;
				}
			}
			return null;
		}
	}

	private static class BufferProvider {
		int[] buffer;
	}	
}
